SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Integer factorization</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Integer factorization</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">"Prime decomposition" redirects here. For the prime decomposition theorem for 3-manifolds, see <a href="Prime_decomposition_of_3-manifolds" title="Prime decomposition of 3-manifolds">Prime decomposition of 3-manifolds</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .unsolved{margin:0.5em 0 1em 1em;border:1px solid #a2a9b1;padding:0.35em 0.35em 0.35em 2.2em;background-color:var(--background-color-interactive-subtle);background-image:url("./mw/Question%2C_Web_Fundamentals.svg");background-position:top 50%left 0.35em;background-size:1.5em;background-repeat:no-repeat}@media(min-width:720px){.mw-parser-output .unsolved{clear:right;float:right;max-width:25%}}.mw-parser-output .unsolved-label{font-weight:bold}.mw-parser-output .unsolved-body{margin:0.35em;font-style:italic}.mw-parser-output .unsolved-more{font-size:smaller}

/* end https://en.wikipedia.org/ */

</style>

<div><span class="unsolved-label" id="unsolved-label-computer_science">Unsolved problem in computer science</span></div>

<div class="unsolved-body">Can integer factorization be solved in polynomial time on a classical computer?</div>

<div class="unsolved-more"><a href="List_of_unsolved_problems_in_computer_science" title="List of unsolved problems in computer science">More unsolved problems in computer science</a></div>

</div>

<p>In <a href="Mathematics" title="Mathematics">mathematics</a>, <b>integer factorization</b> is the decomposition of a <a href="Positive_integer" class="mw-redirect" title="Positive integer">positive integer</a> into a <a href="Product_(mathematics)" title="Product (mathematics)">product</a> of integers. Every positive integer greater than 1 is either the product of two or more integer <a href="Divisor" title="Divisor">factors</a> greater than 1, in which case it is a <a href="Composite_number" title="Composite number">composite number</a>, or it is not, in which case it is a <a href="Prime_number" title="Prime number">prime number</a>. For example, <span class="texhtml">15</span> is a composite number because <span class="texhtml">15 = 3 · 5</span>, but <span class="texhtml">7</span> is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example <span class="texhtml">60 = 3 · 20 = 3 · (5 · 4)</span>. Continuing this process until every factor is prime is called <b>prime factorization</b>; the result is always unique up to the order of the factors by the <a href="Prime_factorization_theorem" class="mw-redirect" title="Prime factorization theorem">prime factorization theorem</a>.

</p><p>To factorize a small integer <span class="texhtml mvar" style="font-style:italic;">n</span> using mental or pen-and-paper arithmetic, the simplest method is <a href="Trial_division" title="Trial division">trial division</a>: checking if the number is divisible by prime numbers <span class="texhtml">2</span>, <span class="texhtml">3</span>, <span class="texhtml">5</span>, and so on, up to the <a href="Square_root" title="Square root">square root</a> of <span class="texhtml mvar" style="font-style:italic;">n</span>. For larger numbers, especially when using a computer, various more sophisticated factorization algorithms are more efficient. A prime factorization algorithm typically involves <a href="Primality_test" title="Primality test">testing whether each factor is prime</a> each time a factor is found.

</p><p>When the numbers are sufficiently large, no efficient non-<a href="Quantum_computer" class="mw-redirect" title="Quantum computer">quantum</a> integer factorization <a href="Algorithm" title="Algorithm">algorithm</a> is known. However, it has not been proven that such an algorithm does not exist. The presumed <a href="Computational_hardness_assumption" title="Computational hardness assumption">difficulty</a> of this problem is important for the algorithms used in <a href="Cryptography" title="Cryptography">cryptography</a> such as <a href="RSA_(cryptosystem)" class="mw-redirect" title="RSA (cryptosystem)">RSA public-key encryption</a> and the <a href="Digital_Signature_Algorithm" title="Digital Signature Algorithm">RSA digital signature</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Many areas of mathematics and <a href="Computer_science" title="Computer science">computer science</a> have been brought to bear on this problem, including <a href="Elliptic_curve" title="Elliptic curve">elliptic curves</a>, <a href="Algebraic_number_theory" title="Algebraic number theory">algebraic number theory</a>, and quantum computing.

</p><p>Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are <a href="Semiprime" title="Semiprime">semiprimes</a>, the product of two prime numbers. When they are both large, for instance more than two thousand <a href="Bit" title="Bit">bits</a> long, randomly chosen, and about the same size (but not too close, for example, to avoid efficient factorization by <a href="Fermat's_factorization_method" title="Fermat's factorization method">Fermat's factorization method</a>), even the fastest prime factorization algorithms on the fastest classical computers can take enough time to make the search impractical; that is, as the number of digits of the integer being factored increases, the number of operations required to perform the factorization on any classical computer increases drastically.

</p><p>Many cryptographic protocols are based on the presumed difficulty of factoring large composite integers or a related problem –for example, the <a href="RSA_problem" title="RSA problem">RSA problem</a>. An algorithm that efficiently factors an arbitrary integer would render <a href="RSA_(algorithm)" class="mw-redirect" title="RSA (algorithm)">RSA</a>-based <a href="Public-key" class="mw-redirect" title="Public-key">public-key</a> cryptography insecure.

</p>

<div class="mw-heading mw-heading2"><h2 id="Prime_decomposition">Prime decomposition</h2></div>

<p>By the <a href="Fundamental_theorem_of_arithmetic" title="Fundamental theorem of arithmetic">fundamental theorem of arithmetic</a>, every positive integer has a unique <a href="Prime_factor" class="mw-redirect" title="Prime factor">prime factorization</a>. (By convention, 1 is the <a href="Empty_product" title="Empty product">empty product</a>.) <a href="Primality_test" title="Primality test">Testing</a> whether the integer is prime can be done in <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a>, for example, by the <a href="AKS_primality_test" title="AKS primality test">AKS primality test</a>. If composite, however, the polynomial time tests give no insight into how to obtain the factors.

</p><p>Given a general algorithm for integer factorization, any integer can be factored into its constituent <a href="Prime_factor" class="mw-redirect" title="Prime factor">prime factors</a> by repeated application of this algorithm. The situation is more complicated with special-purpose factorization algorithms, whose benefits may not be realized as well or even at all with the factors produced during decomposition. For example, if <span class="texhtml"><i>n</i> = 171 × <i>p</i> × <i>q</i></span> where <span class="texhtml"><i>p</i> < <i>q</i></span> are very large primes, <a href="Trial_division" title="Trial division">trial division</a> will quickly produce the factors 3 and 19 but will take <span class="texhtml"><i>p</i></span> divisions to find the next factor. As a contrasting example, if <span class="texhtml"><i>n</i></span> is the product of the primes <span class="texhtml">13729</span>, <span class="texhtml">1372933</span>, and <span class="texhtml">18848997161</span>, where <span class="texhtml">13729 × 1372933 = 18848997157</span>, Fermat's factorization method will begin with <span class="texhtml">⌈<span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>n</i></span></span>⌉ = 18848997159</span> which immediately yields <span class="texhtml"><i>b</i> = <span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>a</i><sup>2</sup> − <i>n</i></span></span> = <span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;">4</span></span> = 2</span> and hence the factors <span class="texhtml"><i>a</i> − <i>b</i> = 18848997157</span> and <span class="texhtml"><i>a</i> + <i>b</i> = 18848997161</span>. While these are easily recognized as composite and prime respectively, Fermat's method will take much longer to factor the composite number because the starting value of <span class="texhtml">⌈<span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;">18848997157</span></span>⌉ = 137292</span> for <span class="texhtml"><i>a</i></span> is a factor of 10 from <span class="texhtml">1372933</span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Current_state_of_the_art">Current state of the art</h2></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Integer_factorization_records" title="Integer factorization records">Integer factorization records</a></div>

<p>Among the <span class="texhtml"><i>b</i></span>-bit numbers, the most difficult to factor in practice using existing algorithms are those <a href="Semiprimes" class="mw-redirect" title="Semiprimes">semiprimes</a> whose factors are of similar size. For this reason, these are the integers used in cryptographic applications.

</p><p>In 2019, a 240-digit (795-bit) number (<a href="RSA-240" class="mw-redirect" title="RSA-240">RSA-240</a>) was factored by a team of researchers including <a href="Paul_Zimmermann_(mathematician)" title="Paul Zimmermann (mathematician)">Paul Zimmermann</a>, utilizing approximately 900 core-years of computing power.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> These researchers estimated that a 1024-bit RSA modulus would take about 500 times as long.<sup id="cite_ref-rsa768_3-0" class="reference"><a href="#cite_note-rsa768-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p><p>The largest such semiprime yet factored was <a href="RSA_numbers#RSA-250" title="RSA numbers">RSA-250</a>, an 829-bit number with 250 decimal digits, in February 2020. The total computation time was roughly 2700 core-years of computing using Intel <a href="Skylake_(microarchitecture)#Xeon_Gold_(quad_processor)" title="Skylake (microarchitecture)">Xeon Gold</a> 6130 at 2.1 GHz. Like all recent factorization records, this factorization was completed with a highly optimized implementation of the <a href="General_number_field_sieve" title="General number field sieve">general number field sieve</a> run on hundreds of machines.

</p>

<div class="mw-heading mw-heading3"><h3 id="Time_complexity">Time complexity</h3></div>

<p>No <a href="Algorithm" title="Algorithm">algorithm</a> has been published that can factor all integers in <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a>, that is, that can factor a <span class="texhtml"><i>b</i></span>-bit number <span class="texhtml"><i>n</i></span> in time <span class="texhtml"><a href="Big_O_notation" title="Big O notation">O</a>(<i>b</i><sup><i>k</i></sup>)</span> for some constant <span class="texhtml"><i>k</i></span>. Neither the existence nor non-existence of such algorithms has been proved, but it is generally suspected that they do not exist.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p><p>There are published algorithms that are faster than <span class="texhtml">O((1 + <i>ε</i>)<sup><i>b</i></sup>)</span> for all positive <span class="texhtml"><i>ε</i></span>, that is, <a href="Time_complexity#Sub-exponential_time" title="Time complexity">sub-exponential</a>. As of 2022, the algorithm with best theoretical asymptotic running time is the <a href="General_number_field_sieve" title="General number field sieve">general number field sieve</a> (GNFS), first published in 1993,<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> running on a <span class="texhtml"><i>b</i></span>-bit number <span class="texhtml"><i>n</i></span> in time:

</p>

<mrow>

<mrow>

<mrow>

<msup>

<mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mrow>

<mfrac>

</mfrac>

</mrow>

</msup>

</mrow>

</mrow>

<msup>

<mrow>

<mrow>

</mrow>

</mrow>

<mfrac>

</mfrac>

</mrow>

</msup>

<msup>

<mrow>

<mrow>

</mrow>

</mrow>

<mfrac>

</mfrac>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \exp \left(\left(\left({\tfrac {8}{3}}\right)^{\frac {2}{3}}+o(1)\right)\left(\log n\right)^{\frac {1}{3}}\left(\log \log n\right)^{\frac {2}{3}}\right).}</annotation>

</semantics>

</math></span><img src="./a7938373b478c57ee7f904580c2ba1ff355d7b33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:45.014ex; height:7.509ex;" alt="{\displaystyle \exp \left(\left(\left({\tfrac {8}{3}}\right)^{\frac {2}{3}}+o(1)\right)\left(\log n\right)^{\frac {1}{3}}\left(\log \log n\right)^{\frac {2}{3}}\right).}" loading="lazy"></span></dd></dl>

<p>For current computers, GNFS is the best published algorithm for large <span class="texhtml"><i>n</i></span> (more than about 400 bits). For a <a href="Quantum_computing" title="Quantum computing">quantum computer</a>, however, <a href="Peter_Shor" title="Peter Shor">Peter Shor</a> discovered an algorithm in 1994 that solves it in polynomial time. <a href="Shor's_algorithm" title="Shor's algorithm">Shor's algorithm</a> takes only <span class="texhtml">O(<i>b</i><sup>3</sup>)</span> time and <span class="texhtml">O(<i>b</i>)</span> space on <span class="texhtml"><i>b</i></span>-bit number inputs. In 2001, Shor's algorithm was implemented for the first time, by using <a href="Nuclear_magnetic_resonance" title="Nuclear magnetic resonance">NMR</a> techniques on molecules that provide seven qubits.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p><p>In order to talk about <a href="Complexity_class" title="Complexity class">complexity classes</a> such as P, NP, and co-NP, the problem has to be stated as a <a href="Decision_problem" title="Decision problem">decision problem</a>.

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .math_theorem{margin:1em 2em;padding:0.5em 1em 0.4em;border:1px solid #aaa;overflow:hidden}@media(max-width:500px){.mw-parser-output .math_theorem{margin:1em 0em;padding:0.5em 0.5em 0.4em}}

/* end https://en.wikipedia.org/ */

</style><div class="math_theorem" style="">

<p><strong class="theorem-name">Decision problem</strong> <span class="theorem-note">(Integer factorization)</span><span class="theoreme-tiret">—</span>For every natural numbers <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>, does <span class="texhtml"><i>n</i></span> have a factor smaller than <span class="texhtml"><i>k</i></span> besides 1?

</p>

</div>

<p>It is known to be in both <a href="NP_(complexity)" title="NP (complexity)">NP</a> and <a href="Co-NP" title="Co-NP">co-NP</a>, meaning that both "yes" and "no" answers can be verified in polynomial time. An answer of "yes" can be certified by exhibiting a factorization <span class="texhtml"><i>n</i> = <i>d</i>(<style data-mw-deduplicate="TemplateStyles:r1214402035">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}

/* end https://en.wikipedia.org/ */

</style><span class="sfrac">⁠<span class="tion"><span class="num"><i>n</i></span><span class="sr-only">/</span><span class="den"><i>d</i></span></span>⁠</span>)</span> with <span class="texhtml"><i>d</i> ≤ <i>k</i></span>. An answer of "no" can be certified by exhibiting the factorization of <span class="texhtml"><i>n</i></span> into distinct primes, all larger than <span class="texhtml"><i>k</i></span>; one can verify their primality using the <a href="AKS_primality_test" title="AKS primality test">AKS primality test</a>, and then multiply them to obtain <span class="texhtml"><i>n</i></span>. The <a href="Fundamental_theorem_of_arithmetic" title="Fundamental theorem of arithmetic">fundamental theorem of arithmetic</a> guarantees that there is only one possible string of increasing primes that will be accepted, which shows that the problem is in both <a href="UP_(complexity)" title="UP (complexity)">UP</a> and co-UP.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> It is known to be in <a href="BQP" title="BQP">BQP</a> because of Shor's algorithm.

</p><p>The problem is suspected to be outside all three of the complexity classes P, NP-complete,<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> and <a href="Co-NP-complete" title="Co-NP-complete">co-NP-complete</a>.

It is therefore a candidate for the <a href="NP-intermediate" title="NP-intermediate">NP-intermediate</a> complexity class.

</p><p>In contrast, the decision problem "Is <span class="texhtml"><i>n</i></span> a composite number?" (or equivalently: "Is <span class="texhtml"><i>n</i></span> a prime number?") appears to be much easier than the problem of specifying factors of <span class="texhtml"><i>n</i></span>. The composite/prime problem can be solved in polynomial time (in the number <span class="texhtml"><i>b</i></span> of digits of <span class="texhtml"><i>n</i></span>) with the <a href="AKS_primality_test" title="AKS primality test">AKS primality test</a>. In addition, there are several <a href="Randomized_algorithm" title="Randomized algorithm">probabilistic algorithms</a> that can test primality very quickly in practice if one is willing to accept a vanishingly small possibility of error. The ease of <a href="Primality_test" title="Primality test">primality testing</a> is a crucial part of the <a href="RSA_(algorithm)" class="mw-redirect" title="RSA (algorithm)">RSA</a> algorithm, as it is necessary to find large prime numbers to start with.

</p>

<div class="mw-heading mw-heading2"><h2 id="Factoring_algorithms">Factoring algorithms</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Special-purpose">Special-purpose</h3></div>

<p>A special-purpose factoring algorithm's running time depends on the properties of the number to be factored or on one of its unknown factors: size, special form, etc. The parameters which determine the running time vary among algorithms.

</p><p>An important subclass of special-purpose factoring algorithms is the <i>Category 1</i> or <i>First Category</i> algorithms, whose running time depends on the size of smallest prime factor. Given an integer of unknown form, these methods are usually applied before general-purpose methods to remove small factors.<sup id="cite_ref-Bressoud_and_Wagon_10-0" class="reference"><a href="#cite_note-Bressoud_and_Wagon-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> For example, naive <a href="Trial_division" title="Trial division">trial division</a> is a Category 1 algorithm.

</p>

<ul><li><a href="Trial_division" title="Trial division">Trial division</a></li>

<li><a href="Wheel_factorization" title="Wheel factorization">Wheel factorization</a></li>

<li><a href="Pollard's_rho_algorithm" title="Pollard's rho algorithm">Pollard's rho algorithm</a>, which has two common flavors to <a href="Cycle_detection" title="Cycle detection">identify group cycles</a>: one by Floyd and one by Brent.</li>

<li><a href="Algebraic-group_factorisation_algorithms" class="mw-redirect" title="Algebraic-group factorisation algorithms">Algebraic-group factorization algorithms</a>, among which are <a href="Pollard's_p_%E2%88%92_1_algorithm" title="Pollard's p − 1 algorithm">Pollard's <span class="texhtml"><i>p</i> − 1</span> algorithm</a>, <a href="Williams'_p_%2B_1_algorithm" class="mw-redirect" title="Williams' p + 1 algorithm">Williams' <span class="texhtml"><i>p</i> + 1</span> algorithm</a>, and <a href="Lenstra_elliptic_curve_factorization" class="mw-redirect" title="Lenstra elliptic curve factorization">Lenstra elliptic curve factorization</a></li>

<li><a href="Fermat's_factorization_method" title="Fermat's factorization method">Fermat's factorization method</a></li>

<li><a href="Euler's_factorization_method" title="Euler's factorization method">Euler's factorization method</a></li>

<li><a href="Special_number_field_sieve" title="Special number field sieve">Special number field sieve</a></li>

<li><a href="Difference_of_two_squares" title="Difference of two squares">Difference of two squares</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="General-purpose">General-purpose</h3></div>

<p>A general-purpose factoring algorithm, also known as a <i>Category 2</i>, <i>Second Category</i>, or <a href="Maurice_Kraitchik" title="Maurice Kraitchik"><i>Kraitchik</i></a> <i>family</i> algorithm,<sup id="cite_ref-Bressoud_and_Wagon_10-1" class="reference"><a href="#cite_note-Bressoud_and_Wagon-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> has a running time which depends solely on the size of the integer to be factored. This is the type of algorithm used to factor <a href="RSA_number" class="mw-redirect" title="RSA number">RSA numbers</a>. Most general-purpose factoring algorithms are based on the <a href="Congruence_of_squares" title="Congruence of squares">congruence of squares</a> method.

</p>

<ul><li><a href="Dixon's_factorization_method" title="Dixon's factorization method">Dixon's factorization method</a></li>

<li><a href="Continued_fraction_factorization" title="Continued fraction factorization">Continued fraction factorization</a> (CFRAC)</li>

<li><a href="Quadratic_sieve" title="Quadratic sieve">Quadratic sieve</a></li>

<li><a href="Rational_sieve" title="Rational sieve">Rational sieve</a></li>

<li><a href="General_number_field_sieve" title="General number field sieve">General number field sieve</a></li>

<li><a href="Shanks's_square_forms_factorization" title="Shanks's square forms factorization">Shanks's square forms factorization</a> (SQUFOF)</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Other_notable_algorithms">Other notable algorithms</h3></div>

<ul><li><a href="Shor's_algorithm" title="Shor's algorithm">Shor's algorithm</a>, for quantum computers</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Heuristic_running_time">Heuristic running time</h2></div>

<p>In number theory, there are many integer factoring algorithms that heuristically have expected <a href="Time_complexity" title="Time complexity">running time</a>

</p>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mrow>

<msup>

<msqrt>

</msqrt>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]=e^{(1+o(1)){\sqrt {(\log n)(\log \log n)}}}}</annotation>

</semantics>

</math></span><img src="./518dd095a6d940c8fa4c133fb2dfd510e9004f1c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:40.254ex; height:4.009ex;" alt="{\displaystyle L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]=e^{(1+o(1)){\sqrt {(\log n)(\log \log n)}}}}" loading="lazy"></span></dd></dl>

<p>in <a href="Big_O_notation" title="Big O notation">little-o</a> and <a href="L-notation" title="L-notation">L-notation</a>.

Some examples of those algorithms are the <a href="Elliptic_curve_method" class="mw-redirect" title="Elliptic curve method">elliptic curve method</a> and the <a href="Quadratic_sieve" title="Quadratic sieve">quadratic sieve</a>.

Another such algorithm is the <b>class group relations method</b> proposed by Schnorr,<sup id="cite_ref-1982-schnorr_11-0" class="reference"><a href="#cite_note-1982-schnorr-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> Seysen,<sup id="cite_ref-1987-seysen_12-0" class="reference"><a href="#cite_note-1987-seysen-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> and Lenstra,<sup id="cite_ref-1988-lenstra_13-0" class="reference"><a href="#cite_note-1988-lenstra-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> which they proved only assuming the unproved <a href="Generalized_Riemann_hypothesis" title="Generalized Riemann hypothesis">generalized Riemann hypothesis</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Rigorous_running_time">Rigorous running time</h2></div>

<p>The Schnorr–Seysen–Lenstra probabilistic algorithm has been rigorously proven by Lenstra and Pomerance<sup id="cite_ref-lenstra-pomerance_14-0" class="reference"><a href="#cite_note-lenstra-pomerance-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> to have expected running time <span class="texhtml"><i>L<sub>n</sub></i>[<span class="sfrac">⁠<span class="tion"><span class="num">1</span><span class="sr-only">/</span><span class="den">2</span></span>⁠</span>, 1+<i>o</i>(1)]</span> by replacing the GRH assumption with the use of multipliers.

The algorithm uses the <a href="Ideal_class_group" title="Ideal class group">class group</a> of positive binary <a href="Quadratic_form" title="Quadratic form">quadratic forms</a> of <a href="Discriminant_of_a_quadratic_form" class="mw-redirect" title="Discriminant of a quadratic form">discriminant</a> <span class="texhtml">Δ</span> denoted by <span class="texhtml"><i>G</i><sub>Δ</sub></span>.

<span class="texhtml"><i>G</i><sub>Δ</sub></span> is the set of triples of integers <span class="texhtml">(<i>a</i>, <i>b</i>, <i>c</i>)</span> in which those integers are relative prime.

</p>

<div class="mw-heading mw-heading3"><h3 id="Schnorr–Seysen–Lenstra_algorithm">Schnorr–Seysen–Lenstra algorithm</h3></div>

<p>Given an integer <span class="texhtml mvar" style="font-style:italic;">n</span> that will be factored, where <span class="texhtml mvar" style="font-style:italic;">n</span> is an odd positive integer greater than a certain constant. In this factoring algorithm the discriminant <span class="texhtml">Δ</span> is chosen as a multiple of <span class="texhtml mvar" style="font-style:italic;">n</span>, <span class="texhtml">Δ = −<i>dn</i></span>, where <span class="texhtml mvar" style="font-style:italic;">d</span> is some positive multiplier. The algorithm expects that for one <span class="texhtml mvar" style="font-style:italic;">d</span> there exist enough <a href="Smooth_number" title="Smooth number">smooth</a> forms in <span class="texhtml"><i>G</i><sub>Δ</sub></span>. Lenstra and Pomerance show that the choice of <span class="texhtml mvar" style="font-style:italic;">d</span> can be restricted to a small set to guarantee the smoothness result.

</p><p>Denote by <span class="texhtml"><i>P</i><sub>Δ</sub></span> the set of all primes <span class="texhtml mvar" style="font-style:italic;">q</span> with <a href="Kronecker_symbol" title="Kronecker symbol">Kronecker symbol</a> <span class="texhtml"><span style="font-size:150%;">(</span><span class="nowrap" style="padding-left:0.1em; padding-right:0.1em;"><span class="sfrac">⁠<span class="tion"><span class="num">Δ</span><span class="sr-only">/</span><span class="den"><i>q</i></span></span>⁠</span></span><span style="font-size:150%;">)</span> = 1</span>. By constructing a set of <a href="Generating_set_of_a_group" title="Generating set of a group">generators</a> of <span class="texhtml"><i>G</i><sub>Δ</sub></span> and prime forms <span class="texhtml"><i>f</i><sub><i>q</i></sub></span> of <span class="texhtml"><i>G</i><sub>Δ</sub></span> with <span class="texhtml mvar" style="font-style:italic;">q</span> in <span class="texhtml"><i>P</i><sub>Δ</sub></span> a sequence of relations between the set of generators and <span class="texhtml"><i>f</i><sub><i>q</i></sub></span> are produced.

The size of <span class="texhtml mvar" style="font-style:italic;">q</span> can be bounded by <span class="texhtml"><i>c</i><sub>0</sub>(log|<span class="nowrap" style="padding-left:0.1em; padding-right:0.1em;">Δ</span>|)<sup>2</sup></span> for some constant <span class="texhtml"><i>c</i><sub>0</sub></span>.

</p><p>The relation that will be used is a relation between the product of powers that is equal to the <a href="Group_(mathematics)" title="Group (mathematics)">neutral element</a> of <span class="texhtml"><i>G</i><sub>Δ</sub></span>. These relations will be used to construct a so-called ambiguous form of <span class="texhtml"><i>G</i><sub>Δ</sub></span>, which is an element of <span class="texhtml"><i>G</i><sub>Δ</sub></span> of order dividing 2. By calculating the corresponding factorization of <span class="texhtml">Δ</span> and by taking a <a href="Greatest_common_divisor" title="Greatest common divisor">gcd</a>, this ambiguous form provides the complete prime factorization of <span class="texhtml mvar" style="font-style:italic;">n</span>. This algorithm has these main steps:

</p><p>Let <span class="texhtml mvar" style="font-style:italic;">n</span> be the number to be factored.

</p>

<div><ol><li>Let <span class="texhtml">Δ</span> be a negative integer with <span class="texhtml">Δ = −<i>dn</i></span>, where <span class="texhtml mvar" style="font-style:italic;">d</span> is a multiplier and <span class="texhtml">Δ</span> is the negative discriminant of some quadratic form.</li><li>Take the <span class="texhtml mvar" style="font-style:italic;">t</span> first primes <span class="texhtml"><i>p</i><sub>1</sub> = 2, <i>p</i><sub>2</sub> = 3, <i>p</i><sub>3</sub> = 5, ..., <i>p</i><sub><i>t</i></sub></span>, for some <span class="texhtml"><i>t</i> ∈ <b>N</b></span>.</li><li>Let <span class="texhtml"><i>f</i><sub><i>q</i></sub></span> be a random prime form of <span class="texhtml"><i>G</i><sub>Δ</sub></span> with <span class="texhtml"><span style="font-size:150%;">(</span><span class="nowrap" style="padding-left:0.1em; padding-right:0.1em;"><span class="sfrac">⁠<span class="tion"><span class="num">Δ</span><span class="sr-only">/</span><span class="den"><i>q</i></span></span>⁠</span></span><span style="font-size:150%;">)</span> = 1</span>.</li><li>Find a generating set <span class="texhtml mvar" style="font-style:italic;">X</span> of <span class="texhtml"><i>G</i><sub>Δ</sub></span>.</li><li>Collect a sequence of relations between set <span class="texhtml mvar" style="font-style:italic;">X</span> and <span class="texhtml">{<i>f</i><sub><i>q</i></sub> : <i>q</i> ∈ <i>P</i><sub>Δ</sub>}</span> satisfying:

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1.}</annotation>

</semantics>

</math></span><img src="./8cf163246a6d632cc54541e523589f0817de26e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:30.791ex; height:7.843ex;" alt="{\displaystyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1.}" loading="lazy"></span></dd></dl></li><li>Construct an ambiguous form <span class="texhtml">(<i>a</i>, <i>b</i>, <i>c</i>)</span> that is an element <span class="texhtml"><i>f</i> ∈ <i>G</i><sub>Δ</sub></span> of order dividing 2 to obtain a coprime factorization of the largest odd divisor of <span class="texhtml">Δ</span> in which <span class="texhtml">Δ = −4<i>ac</i></span> or <span class="texhtml">Δ = <i>a</i>(<i>a</i> − 4<i>c</i>)</span> or <span class="texhtml">Δ = (<i>b</i> − 2<i>a</i>)(<i>b</i> + 2<i>a</i>)</span>.</li><li>If the ambiguous form provides a factorization of <span class="texhtml mvar" style="font-style:italic;">n</span> then stop, otherwise find another ambiguous form until the factorization of <span class="texhtml mvar" style="font-style:italic;">n</span> is found. In order to prevent useless ambiguous forms from generating, build up the <a href="Sylow_theorems" title="Sylow theorems">2-Sylow</a> group <span class="texhtml">Sll<sub>2</sub>(Δ)</span> of <span class="texhtml"><i>G</i>(Δ)</span>.</li></ol></div>

<p>To obtain an algorithm for factoring any positive integer, it is necessary to add a few steps to this algorithm such as trial division, and the <a href="Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test" title="Adleman–Pomerance–Rumely primality test">Jacobi sum test</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Expected_running_time">Expected running time</h3></div>

<p>The algorithm as stated is a <a href="Probabilistic_algorithm" class="mw-redirect" title="Probabilistic algorithm">probabilistic algorithm</a> as it makes random choices. Its expected running time is at most <span class="texhtml"><i>L<sub>n</sub></i>[<span class="sfrac">⁠<span class="tion"><span class="num">1</span><span class="sr-only">/</span><span class="den">2</span></span>⁠</span>, 1+<i>o</i>(1)]</span>.<sup id="cite_ref-lenstra-pomerance_14-1" class="reference"><a href="#cite_note-lenstra-pomerance-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Aurifeuillean_factorization" title="Aurifeuillean factorization">Aurifeuillean factorization</a></li>

<li><a href="Bach's_algorithm" title="Bach's algorithm">Bach's algorithm</a> for generating random numbers with their factorizations</li>

<li><a href="Canonical_representation_of_a_positive_integer" class="mw-redirect" title="Canonical representation of a positive integer">Canonical representation of a positive integer</a></li>

<li><a href="Factorization" title="Factorization">Factorization</a></li>

<li><a href="Multiplicative_partition" title="Multiplicative partition">Multiplicative partition</a></li>

<li><a href="P-adic_valuation" title="P-adic valuation"><span class="texhtml mvar" style="font-style:italic;">p</span>-adic valuation</a></li>

<li><a href="Integer_partition" title="Integer partition">Integer partition</a> – a way of writing a number as a sum of positive integers.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFLenstra2011" class="citation cs2">Lenstra, Arjen K. (2011), "Integer Factoring", in van Tilborg, Henk C. A.; Jajodia, Sushil (eds.), <i>Encyclopedia of Cryptography and Security</i>, Boston: Springer, pp. <span class="nowrap">611–</span>618, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4419-5906-5_455">10.1007/978-1-4419-5906-5_455</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4419-5905-8</bdi></cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20191202190004/https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-December/001139.html">"[Cado-nfs-discuss] 795-bit factoring and discrete logarithms"</a>. Archived from <a rel="nofollow" class="external text" href="https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-December/001139.html">the original</a> on 2019-12-02.</cite></span>

</li>

<li id="cite_note-rsa768-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-rsa768_3-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFKleinjungAokiFrankeLenstra2010" class="citation conference cs1">Kleinjung, Thorsten; Aoki, Kazumaro; Franke, Jens; Lenstra, Arjen K.; Thomé, Emmanuel; Bos, Joppe W.; Gaudry, Pierrick; Kruppa, Alexander; Montgomery, Peter L.; Osvik, Dag Arne; te Riele, Herman J. J.; Timofeev, Andrey; Zimmermann, Paul (2010). <a rel="nofollow" class="external text" href="https://eprint.iacr.org/2010/006.pdf">"Factorization of a 768-Bit RSA Modulus"</a> <span class="cs1-format">(PDF)</span>. In Rabin, Tal (ed.). <i>Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings</i>. Lecture Notes in Computer Science. Vol. 6223. Springer. pp. <span class="nowrap">333–</span>350. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-14623-7_18">10.1007/978-3-642-14623-7_18</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-14622-0</bdi>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFKrantz2011" class="citation cs2"><a href="Steven_G._Krantz" title="Steven G. Krantz">Krantz, Steven G.</a> (2011), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=mMZBtxVZiQoC&pg=PA203"><i>The Proof is in the Pudding: The Changing Nature of Mathematical Proof</i></a>, New York: Springer, p. 203, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-0-387-48744-1">10.1007/978-0-387-48744-1</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-48908-7</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2789493">2789493</a></cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFAroraBarak2009" class="citation cs2"><a href="Sanjeev_Arora" title="Sanjeev Arora">Arora, Sanjeev</a>; Barak, Boaz (2009), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=nGvI7cOuOOQC&pg=PA230"><i>Computational complexity</i></a>, Cambridge: Cambridge University Press, p. 230, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FCBO9780511804090">10.1017/CBO9780511804090</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-42426-4</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2500087">2500087</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:215746906">215746906</a></cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFBuhlerLenstraPomerance1993" class="citation book cs1">Buhler, J. P.; Lenstra, H. W. Jr.; Pomerance, Carl (1993). "Factoring integers with the number field sieve". <a rel="nofollow" class="external text" href="https://doi.org/10.1007/BFb0091539"><i>The development of the number field sieve</i></a>. Lecture Notes in Mathematics. Vol. 1554. Springer. pp. <span class="nowrap">50–</span>94. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBFb0091539">10.1007/BFb0091539</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1887%2F2149">1887/2149</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-57013-4</bdi><span class="reference-accessdate">. Retrieved <span class="nowrap">12 March</span> 2021</span>.</cite></span>

</li>

<cite id="CITEREFVandersypen2001" class="citation journal cs1">Vandersypen, Lieven M. K.; et al. (2001). "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance". <i><a href="Nature_(journal)" title="Nature (journal)">Nature</a></i>. <b>414</b> (6866): <span class="nowrap">883–</span>887. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0112176">quant-ph/0112176</a></span>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2001Natur.414..883V">2001Natur.414..883V</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2F414883a">10.1038/414883a</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/11780055">11780055</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:4400832">4400832</a>.</cite></span>

</li>

<cite id="CITEREFLance_Fortnow2002" class="citation web cs1">Lance Fortnow (2002-09-13). <a rel="nofollow" class="external text" href="http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html">"Computational Complexity Blog: Complexity Class of the Week: Factoring"</a>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFGoldreichWigderson2008" class="citation cs2"><a href="Oded_Goldreich" title="Oded Goldreich">Goldreich, Oded</a>; <a href="Avi_Wigderson" title="Avi Wigderson">Wigderson, Avi</a> (2008), "IV.20 Computational Complexity", in <a href="Timothy_Gowers" title="Timothy Gowers">Gowers, Timothy</a>; <a href="June_Barrow-Green" title="June Barrow-Green">Barrow-Green, June</a>; <a href="Imre_Leader" title="Imre Leader">Leader, Imre</a> (eds.), <i>The Princeton Companion to Mathematics</i>, Princeton, New Jersey: Princeton University Press, pp. <span class="nowrap">575–</span>604, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-691-11880-2</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2467561">2467561</a></cite>. See in particular <a rel="nofollow" class="external text" href="https://books.google.com/books?id=ZOfUsvemJDMC&pg=PA583">p. 583</a>.</span>

</li>

<cite id="CITEREFDavid_Bressoud_and_Stan_Wagon2000" class="citation book cs1"><a href="David_Bressoud" title="David Bressoud">David Bressoud</a> and <a href="Stan_Wagon" title="Stan Wagon">Stan Wagon</a> (2000). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/courseincomputat0000bres/page/168"><i>A Course in Computational Number Theory</i></a></span>. Key College Publishing/Springer. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/courseincomputat0000bres/page/168">168–69</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-930190-10-8</bdi>.</cite></span>

</li>

<li id="cite_note-1982-schnorr-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-1982-schnorr_11-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFSchnorr1982" class="citation journal cs1">Schnorr, Claus P. (1982). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170924140543/http://www.dtic.mil/get-tr-doc/pdf?AD=ADA096348">"Refined analysis and improvements on some factoring algorithms"</a>. <i>Journal of Algorithms</i>. <b>3</b> (2): <span class="nowrap">101–</span>127. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0196-6774%2882%2990012-8">10.1016/0196-6774(82)90012-8</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0657269">0657269</a>. Archived from <a rel="nofollow" class="external text" href="http://www.dtic.mil/get-tr-doc/pdf?AD=ADA096348">the original</a> on September 24, 2017.</cite></span>

</li>

<li id="cite_note-1987-seysen-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-1987-seysen_12-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFSeysen1987" class="citation journal cs1">Seysen, Martin (1987). <a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0025-5718-1987-0878705-X">"A probabilistic factorization algorithm with quadratic forms of negative discriminant"</a>. <i>Mathematics of Computation</i>. <b>48</b> (178): <span class="nowrap">757–</span>780. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0025-5718-1987-0878705-X">10.1090/S0025-5718-1987-0878705-X</a></span>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0878705">0878705</a>.</cite></span>

</li>

<li id="cite_note-1988-lenstra-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-1988-lenstra_13-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFLenstra1988" class="citation journal cs1">Lenstra, Arjen K (1988). <a rel="nofollow" class="external text" href="https://infoscience.epfl.ch/record/164491/files/nscan9.PDF">"Fast and rigorous factorization under the generalized Riemann hypothesis"</a> <span class="cs1-format">(PDF)</span>. <i>Indagationes Mathematicae</i>. <b>50</b> (4): <span class="nowrap">443–</span>454. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS1385-7258%2888%2980022-2">10.1016/S1385-7258(88)80022-2</a>.</cite></span>

</li>

<li id="cite_note-lenstra-pomerance-14"><span class="mw-cite-backlink">^ <a href="#cite_ref-lenstra-pomerance_14-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-lenstra-pomerance_14-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFLenstraPomerance1992" class="citation journal cs1">Lenstra, H. W.; Pomerance, Carl (July 1992). <a rel="nofollow" class="external text" href="https://www.ams.org/journals/jams/1992-05-03/S0894-0347-1992-1137100-0/S0894-0347-1992-1137100-0.pdf">"A Rigorous Time Bound for Factoring Integers"</a> <span class="cs1-format">(PDF)</span>. <i>Journal of the American Mathematical Society</i>. <b>5</b> (3): <span class="nowrap">483–</span>516. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0894-0347-1992-1137100-0">10.1090/S0894-0347-1992-1137100-0</a></span>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1137100">1137100</a>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFRichard_Crandall_and_Carl_Pomerance2001" class="citation book cs1"><a href="Richard_Crandall" title="Richard Crandall">Richard Crandall</a> and <a href="Carl_Pomerance" title="Carl Pomerance">Carl Pomerance</a> (2001). <i>Prime Numbers: A Computational Perspective</i>. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-94777-9</bdi>.</cite> Chapter 5: Exponential Factoring Algorithms, pp. 191–226. Chapter 6: Subexponential Factoring Algorithms, pp. 227–284. Section 7.4: Elliptic curve method, pp. 301–313.</li>

<li><a href="Donald_Knuth" title="Donald Knuth">Donald Knuth</a>. <i><a href="The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a></i>, Volume 2: <i>Seminumerical Algorithms</i>, Third Edition. Addison-Wesley, 1997. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-89684-2</bdi>. Section 4.5.4: Factoring into Primes, pp. 379–417.</li>

<li><cite id="CITEREFSamuel_S._Wagstaff_Jr.2013" class="citation book cs1"><a href="Samuel_S._Wagstaff_Jr." title="Samuel S. Wagstaff Jr.">Samuel S. Wagstaff Jr.</a> (2013). <a rel="nofollow" class="external text" href="https://www.ams.org/bookpages/stml-68"><i>The Joy of Factoring</i></a>. Providence, RI: American Mathematical Society. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4704-1048-3</bdi>.</cite>.</li>

<li><cite id="CITEREFWarren2013" class="citation book cs1">Warren, Henry S. Jr. (2013). <i><a href="Hacker's_Delight" title="Hacker's Delight">Hacker's Delight</a></i> (2 ed.). <a href="Addison_Wesley" class="mw-redirect" title="Addison Wesley">Addison Wesley</a> - <a href="Pearson_Education%2C_Inc." class="mw-redirect" title="Pearson Education, Inc.">Pearson Education, Inc.</a> <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-321-84268-8</bdi>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://sourceforge.net/projects/msieve/">msieve</a> – SIQS and NFS – has helped complete some of the largest public factorizations known</li>

<li>Richard P. Brent, "Recent Progress and Prospects for Integer Factorisation Algorithms", <i>Computing and Combinatorics"</i>, 2000, pp. 3–22. <a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/327036.html">download</a></li>

<li><a href="Manindra_Agrawal" title="Manindra Agrawal">Manindra Agrawal</a>, Neeraj Kayal, Nitin Saxena, "PRIMES is in P." Annals of Mathematics 160(2): 781–793 (2004). <a rel="nofollow" class="external text" href="http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf">August 2005 version PDF</a></li>

<li>Eric W. Weisstein, <a rel="nofollow" class="external text" href="http://mathworld.wolfram.com/news/2005-11-08/rsa-640/">“RSA-640 Factored” <i>MathWorld Headline News</i>, November 8, 2005</a></li>

<li><a rel="nofollow" class="external text" href="https://www.alpertron.com.ar/ECM.HTM">Dario Alpern's Integer factorization calculator</a> – A web app for factoring large integers</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Computational_hardness_assumptions136" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Computational_hardness_assumptions136" style="font-size:114%;margin:0 4em"><a href="Computational_hardness_assumption" title="Computational hardness assumption">Computational hardness assumptions</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Number theoretic</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul>

<li><a href="Phi-hiding_assumption" title="Phi-hiding assumption">Phi-hiding</a></li>

<li><a href="RSA_problem" title="RSA problem">RSA problem</a></li>

<li><a href="Strong_RSA_assumption" title="Strong RSA assumption">Strong RSA</a></li>

<li><a href="Quadratic_residuosity_problem" title="Quadratic residuosity problem">Quadratic residuosity</a></li>

<li><a href="Decisional_composite_residuosity_assumption" title="Decisional composite residuosity assumption">Decisional composite residuosity</a></li>

<li><a href="Higher_residuosity_problem" title="Higher residuosity problem">Higher residuosity</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Group theoretic</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Discrete_logarithm#Cryptography" title="Discrete logarithm">Discrete logarithm</a></li>

<li><a href="Diffie%E2%80%93Hellman_problem" title="Diffie–Hellman problem">Diffie-Hellman</a></li>

<li><a href="Decisional_Diffie%E2%80%93Hellman_assumption" title="Decisional Diffie–Hellman assumption">Decisional Diffie–Hellman</a></li>

<li><a href="Computational_Diffie%E2%80%93Hellman_assumption" title="Computational Diffie–Hellman assumption">Computational Diffie–Hellman</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Pairings</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="XDH_assumption" title="XDH assumption">External Diffie–Hellman</a></li>

<li><a href="Sub-group_hiding" title="Sub-group hiding">Sub-group hiding</a></li>

<li><a href="Decision_Linear_assumption" title="Decision Linear assumption">Decision linear</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Lattices</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Lattice_problem#Shortest_vector_problem_(SVP)" title="Lattice problem">Shortest vector problem</a> (<a href="Lattice_problem#GapSVP" title="Lattice problem">gap</a>)</li>

<li><a href="Lattice_problem#Closest_vector_problem_(CVP)" title="Lattice problem">Closest vector problem</a> (<a href="Lattice_problem#GapCVP" title="Lattice problem">gap</a>)</li>

<li><a href="Learning_with_errors" title="Learning with errors">Learning with errors</a></li>

<li><a href="Ring_learning_with_errors" title="Ring learning with errors">Ring learning with errors</a></li>

<li><a href="Short_integer_solution_problem" title="Short integer solution problem">Short integer solution</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Non-cryptographic</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Exponential_time_hypothesis" title="Exponential time hypothesis">Exponential time hypothesis</a></li>

<li><a href="Unique_games_conjecture" title="Unique games conjecture">Unique games conjecture</a></li>

<li><a href="Planted_clique" title="Planted clique">Planted clique conjecture</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Number-theoretic_algorithms413" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Number-theoretic_algorithms413" style="font-size:114%;margin:0 4em"><a href="Number_theory" title="Number theory">Number-theoretic</a> <a href="Algorithm" title="Algorithm">algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Primality_test" title="Primality test">Primality tests</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Baillie%E2%80%93PSW_primality_test" title="Baillie–PSW primality test">Baillie–PSW</a></li>

<li><a href="Elliptic_curve_primality" title="Elliptic curve primality">Elliptic curve</a></li>

<li><a href="Pocklington_primality_test" title="Pocklington primality test">Pocklington</a></li>

<li><a href="Fermat_primality_test" title="Fermat primality test">Fermat</a></li>

<li><a href="Lucas_primality_test" title="Lucas primality test">Lucas</a></li>

<li><i><a href="Lucas%E2%80%93Lehmer_primality_test" title="Lucas–Lehmer primality test">Lucas–Lehmer</a></i></li>

<li><i><a href="Lucas%E2%80%93Lehmer%E2%80%93Riesel_test" title="Lucas–Lehmer–Riesel test">Lucas–Lehmer–Riesel</a></i></li>

<li><i><a href="Proth's_theorem" title="Proth's theorem">Proth's theorem</a></i></li>

<li><i><a href="P%C3%A9pin's_test" title="Pépin's test">Pépin's</a></i></li>

<li><a href="Quadratic_Frobenius_test" title="Quadratic Frobenius test">Quadratic Frobenius</a></li>

<li><a href="Solovay%E2%80%93Strassen_primality_test" title="Solovay–Strassen primality test">Solovay–Strassen</a></li>

<li><a href="Miller%E2%80%93Rabin_primality_test" title="Miller–Rabin primality test">Miller–Rabin</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Generating_primes" class="mw-redirect" title="Generating primes">Prime-generating</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Sieve_of_Atkin" title="Sieve of Atkin">Sieve of Atkin</a></li>

<li><a href="Sieve_of_Eratosthenes" title="Sieve of Eratosthenes">Sieve of Eratosthenes</a></li>

<li><a href="Sieve_of_Pritchard" title="Sieve of Pritchard">Sieve of Pritchard</a></li>

<li><a href="Sieve_of_Sundaram" title="Sieve of Sundaram">Sieve of Sundaram</a></li>

<li><a href="Wheel_factorization" title="Wheel factorization">Wheel factorization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Continued_fraction_factorization" title="Continued fraction factorization">Continued fraction (CFRAC)</a></li>

<li><a href="Dixon's_factorization_method" title="Dixon's factorization method">Dixon's</a></li>

<li><a href="Lenstra_elliptic-curve_factorization" title="Lenstra elliptic-curve factorization">Lenstra elliptic curve (ECM)</a></li>

<li><a href="Euler's_factorization_method" title="Euler's factorization method">Euler's</a></li>

<li><a href="Pollard's_rho_algorithm" title="Pollard's rho algorithm">Pollard's rho</a></li>

<li><a href="Quadratic_sieve" title="Quadratic sieve">Quadratic sieve (QS)</a></li>

<li><a href="General_number_field_sieve" title="General number field sieve">General number field sieve (GNFS)</a></li>

<li><i><a href="Special_number_field_sieve" title="Special number field sieve">Special number field sieve (SNFS)</a></i></li>

<li><a href="Rational_sieve" title="Rational sieve">Rational sieve</a></li>

<li><a href="Fermat's_factorization_method" title="Fermat's factorization method">Fermat's</a></li>

<li><a href="Shanks's_square_forms_factorization" title="Shanks's square forms factorization">Shanks's square forms</a></li>

<li><a href="Trial_division" title="Trial division">Trial division</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Multiplication_algorithm" title="Multiplication algorithm">Multiplication</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Ancient_Egyptian_multiplication" title="Ancient Egyptian multiplication">Ancient Egyptian</a></li>

<li><a href="Karatsuba_algorithm" title="Karatsuba algorithm">Karatsuba</a></li>

<li><a href="Sch%C3%B6nhage%E2%80%93Strassen_algorithm" title="Schönhage–Strassen algorithm">Schönhage–Strassen</a></li>

<li><a href="F%C3%BCrer's_algorithm" class="mw-redirect" title="Fürer's algorithm">Fürer's</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Euclidean_division" title="Euclidean division">Euclidean</a> <a href="Division_algorithm" title="Division algorithm">division</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_division" class="mw-redirect" title="Binary division">Binary</a></li>

<li><a href="Chunking_(division)" title="Chunking (division)">Chunking</a></li>

<li><a href="Fourier_division" title="Fourier division">Fourier</a></li>

<li><a href="Goldschmidt_division" class="mw-redirect" title="Goldschmidt division">Goldschmidt</a></li>

<li><a href="Newton%E2%80%93Raphson_division" class="mw-redirect" title="Newton–Raphson division">Newton-Raphson</a></li>

<li><a href="Short_division" title="Short division">Short</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Discrete_logarithm" title="Discrete logarithm">Discrete logarithm</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Baby-step_giant-step" title="Baby-step giant-step">Baby-step giant-step</a></li>

<li><a href="Pollard's_rho_algorithm_for_logarithms" title="Pollard's rho algorithm for logarithms">Pollard rho</a></li>

<li><a href="Pollard's_kangaroo_algorithm" title="Pollard's kangaroo algorithm">Pollard kangaroo</a></li>

<li><a href="Pohlig%E2%80%93Hellman_algorithm" title="Pohlig–Hellman algorithm">Pohlig–Hellman</a></li>

<li><a href="Index_calculus_algorithm" title="Index calculus algorithm">Index calculus</a></li>

<li><a href="Function_field_sieve" title="Function field sieve">Function field sieve</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Greatest_common_divisor" title="Greatest common divisor">Greatest common divisor</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_GCD_algorithm" title="Binary GCD algorithm">Binary</a></li>

<li><a href="Euclidean_algorithm" title="Euclidean algorithm">Euclidean</a></li>

<li><a href="Extended_Euclidean_algorithm" title="Extended Euclidean algorithm">Extended Euclidean</a></li>

<li><a href="Lehmer's_GCD_algorithm" title="Lehmer's GCD algorithm">Lehmer's</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quadratic_residue" title="Quadratic residue">Modular square root</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cipolla's_algorithm" title="Cipolla's algorithm">Cipolla</a></li>

<li><a href="Pocklington's_algorithm" title="Pocklington's algorithm">Pocklington's</a></li>

<li><a href="Tonelli%E2%80%93Shanks_algorithm" title="Tonelli–Shanks algorithm">Tonelli–Shanks</a></li>

<li><a href="Berlekamp%E2%80%93Rabin_algorithm" title="Berlekamp–Rabin algorithm">Berlekamp</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other algorithms</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Chakravala_method" title="Chakravala method">Chakravala</a></li>

<li><a href="Cornacchia's_algorithm" title="Cornacchia's algorithm">Cornacchia</a></li>

<li><a href="Exponentiation_by_squaring" title="Exponentiation by squaring">Exponentiation by squaring</a></li>

<li><a href="Integer_square_root" title="Integer square root">Integer square root</a></li>

<li><a href="Integer_relation_algorithm" title="Integer relation algorithm">Integer relation</a> (<a href="Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm" title="Lenstra–Lenstra–Lovász lattice basis reduction algorithm">LLL</a>; <a href="Korkine%E2%80%93Zolotarev_lattice_basis_reduction_algorithm" title="Korkine–Zolotarev lattice basis reduction algorithm">KZ</a>)</li>

<li><a href="Modular_exponentiation" title="Modular exponentiation">Modular exponentiation</a></li>

<li><a href="Montgomery_reduction" class="mw-redirect" title="Montgomery reduction">Montgomery reduction</a></li>

<li><a href="Schoof's_algorithm" title="Schoof's algorithm">Schoof</a></li>

<li><a href="Trachtenberg_system" title="Trachtenberg system">Trachtenberg system</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow hlist" colspan="2"><div>

<ul><li><i>Italics</i> indicate that algorithm is for numbers of special forms</li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Divisibility-based_sets_of_integers166" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="3"><div id="Divisibility-based_sets_of_integers166" style="font-size:114%;margin:0 4em">Divisibility-based sets of integers</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Overview</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul>

<li><a href="Divisor" title="Divisor">Divisor</a></li>

<li><a href="Unitary_divisor" title="Unitary divisor">Unitary divisor</a></li>

<li><a href="Divisor_function" title="Divisor function">Divisor function</a></li>

<li><a href="Prime_factor" class="mw-redirect" title="Prime factor">Prime factor</a></li>

<li><a href="Fundamental_theorem_of_arithmetic" title="Fundamental theorem of arithmetic">Fundamental theorem of arithmetic</a></li></ul>

</div></td><td class="noviewer navbox-image" rowspan="7" style="width:1px;padding:0 0 0 2px"><div><span typeof="mw:File"></span></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Factorization forms</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Prime_number" title="Prime number">Prime</a></li>

<li><a href="Composite_number" title="Composite number">Composite</a></li>

<li><a href="Semiprime" title="Semiprime">Semiprime</a></li>

<li><a href="Pronic_number" title="Pronic number">Pronic</a></li>

<li><a href="Sphenic_number" title="Sphenic number">Sphenic</a></li>

<li><a href="Square-free_integer" title="Square-free integer">Square-free</a></li>

<li><a href="Powerful_number" title="Powerful number">Powerful</a></li>

<li><a href="Perfect_power" title="Perfect power">Perfect power</a></li>

<li><a href="Achilles_number" title="Achilles number">Achilles</a></li>

<li><a href="Smooth_number" title="Smooth number">Smooth</a></li>

<li><a href="Regular_number" title="Regular number">Regular</a></li>

<li><a href="Rough_number" title="Rough number">Rough</a></li>

<li><a href="Unusual_number" title="Unusual number">Unusual</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Constrained divisor sums</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Perfect_number" title="Perfect number">Perfect</a></li>

<li><a href="Almost_perfect_number" title="Almost perfect number">Almost perfect</a></li>

<li><a href="Quasiperfect_number" title="Quasiperfect number">Quasiperfect</a></li>

<li><a href="Multiply_perfect_number" title="Multiply perfect number">Multiply perfect</a></li>

<li><a href="Hemiperfect_number" title="Hemiperfect number">Hemiperfect</a></li>

<li><a href="Hyperperfect_number" title="Hyperperfect number">Hyperperfect</a></li>

<li><a href="Superperfect_number" title="Superperfect number">Superperfect</a></li>

<li><a href="Unitary_perfect_number" title="Unitary perfect number">Unitary perfect</a></li>

<li><a href="Semiperfect_number" title="Semiperfect number">Semiperfect</a></li>

<li><a href="Practical_number" title="Practical number">Practical</a></li>

<li><a href="Descartes_number" title="Descartes number">Descartes</a></li>

<li><a href="Erd%C5%91s%E2%80%93Nicolas_number" title="Erdős–Nicolas number">Erdős–Nicolas</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">With many divisors</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Abundant_number" title="Abundant number">Abundant</a></li>

<li><a href="Primitive_abundant_number" title="Primitive abundant number">Primitive abundant</a></li>

<li><a href="Highly_abundant_number" title="Highly abundant number">Highly abundant</a></li>

<li><a href="Superabundant_number" title="Superabundant number">Superabundant</a></li>

<li><a href="Colossally_abundant_number" title="Colossally abundant number">Colossally abundant</a></li>

<li><a href="Highly_composite_number" title="Highly composite number">Highly composite</a></li>

<li><a href="Superior_highly_composite_number" title="Superior highly composite number">Superior highly composite</a></li>

<li><a href="Weird_number" title="Weird number">Weird</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Aliquot_sequence" title="Aliquot sequence">Aliquot sequence</a>-related</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Untouchable_number" title="Untouchable number">Untouchable</a></li>

<li><a href="Amicable_numbers" title="Amicable numbers">Amicable</a> (<a href="Amicable_triple" title="Amicable triple">Triple</a>)</li>

<li><a href="Sociable_number" title="Sociable number">Sociable</a></li>

<li><a href="Betrothed_numbers" title="Betrothed numbers">Betrothed</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Radix" title="Radix">Base</a>-dependent</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Equidigital_number" title="Equidigital number">Equidigital</a></li>

<li><a href="Extravagant_number" title="Extravagant number">Extravagant</a></li>

<li><a href="Frugal_number" title="Frugal number">Frugal</a></li>

<li><a href="Harshad_number" title="Harshad number">Harshad</a></li>

<li><a href="Polydivisible_number" title="Polydivisible number">Polydivisible</a></li>

<li><a href="Smith_number" title="Smith number">Smith</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other sets</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Arithmetic_number" title="Arithmetic number">Arithmetic</a></li>

<li><a href="Deficient_number" title="Deficient number">Deficient</a></li>

<li><a href="Friendly_number" title="Friendly number">Friendly</a></li>

<li><a href="Friendly_number#Solitary_numbers" title="Friendly number">Solitary</a></li>

<li><a href="Sublime_number" title="Sublime number">Sublime</a></li>

<li><a href="Harmonic_divisor_number" title="Harmonic divisor number">Harmonic divisor</a></li>

<li><a href="Refactorable_number" title="Refactorable number">Refactorable</a></li>

<li><a href="Superperfect_number" title="Superperfect number">Superperfect</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox authority-control" aria-label="Navbox391" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Authority control databases: National </th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4175717-8">Germany</a></span></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-19" href="https://en.wikipedia.org/wiki/?title=Integer_factorization&oldid=1296409037">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>